#!/usr/bin/env python
# encoding: utf-8
'''
@author: Excelsiorly
@license: (C) Copyright 2022, All Rights Reserved.
@contact: excelsiorly@qq.com
@file: 025. K 个一组翻转链表
@time: 2022/1/5 14:44
@desc: https://leetcode-cn.com/problems/reverse-nodes-in-k-group/
给你一个链表，每 k 个节点一组进行翻转，请你返回翻转后的链表。

k 是一个正整数，它的值小于或等于链表的长度。

如果节点总数不是 k 的整数倍，那么请将最后剩余的节点保持原有顺序。

进阶：
● 你可以设计一个只使用常数额外空间的算法来解决此问题吗？
● 你不能只是单纯的改变节点内部的值，而是需要实际进行节点交换。
@解题思路：
    1. 局部子链的反转(leetcode 215)
    2. 每次翻转前检查还有无k个元素可以操作
    3. 注意局部子链翻转的循环退出条件

1. Ot(n), Os(1)
'''
# Definition for singly-linked list.
class ListNode(object):
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

class Solution(object):
    def reverse(self, head, tail):
        p, pre = head, tail.next  # 当p在head的时候，他的next就是最开始tail的next，也就是下一组链表的头
        # 退出条件是p走出了[head, tail]区间，此时pre在tail的位置
        while pre != tail:
            next = p.next
            p.next = pre
            pre = p
            p = next
        return tail, head

    def reverseKGroup(self, head, k):
        """
        :type head: ListNode
        :type k: int
        :rtype: ListNode
        """
        dummy = ListNode(0)
        dummy.next = head
        pre = dummy

        while head:
            # tail记录上一条子链的尾结点
            tail = pre
            # 检查当前子链是否有k个结点
            for _ in range(k):
                tail = tail.next
                # 若当前子链已无k个结点了则直接返回头节点
                if not tail:
                    return dummy.next
            # 此时tail已经来到了当前子链的第k个结点
            # nex用来记录下一个子链的头节点
            nex = tail.next
            head, tail = self.reverse(head, tail)  # reverse用来反转head->tail的子链
            # 链接上下子链
            pre.next = head
            tail.next = nex
            pre = tail
            head = tail.next

        return dummy.next


if __name__ == '__main__':
    head = ListNode(1)
    head.next = ListNode(2)
    head.next.next = ListNode(3)
    head.next.next.next = ListNode(4)
    head.next.next.next.next = ListNode(5)
    k = 2
    res = Solution().reverseKGroup(head, k)
    print(res)